/*
 Copyright Remco Schoeman

 */
using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Needle.Utils.Collections
{
    /// <summary>
    /// A collection that uses weak references to its items.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <remarks>
    /// Removal of dead references is done when any of the ICollection interface methods are called;
    /// The properties are 'side-effect' free.
    /// </remarks>
    [DebuggerTypeProxy("Needle.Utils.Collections.WeakList<>.DebuggerProxy")]
    public class WeakList<T> : ICollection<T> where T : class
    {
        private static EqualityComparer<T> _comparer = EqualityComparer<T>.Default;
                    

        #region  List node structure
        [DebuggerDisplay("{(Ref != null) ? (IsAlive ? \"Alive\" : \" Dead\") : \"-----\",nq}, Next: {Next}, Target: {Target}")]
        private struct Node
        {

            public int Next;
            public WeakReference Ref;

            public Node(int next)
            {
                this.Next = next;
                this.Ref = null;
            }

            public Node(T item, int next)
            {
                Ensure.NotNull(item, "item");
                this.Next = next;
                this.Ref = new WeakReference(item);
            }

            public Node(T item, int next, bool trackResurrection)
            {
                Ensure.NotNull(item, "item");
                this.Ref = new WeakReference(item, trackResurrection);
                this.Next = next;
            }

            public bool IsAlive
            {
                get { return (Ref == null) ? false : Ref.IsAlive; }
            }

            public T Target
            {
                get { return (Ref == null) ? null : Ref.Target as T; }
            }
        }

        #endregion

        #region Debugger proxy

        private class DebuggerProxy
        {
            WeakList<T> list;
            public DebuggerProxy(WeakList<T> list)
            {
                this.list = list;
            }

            public int Count { get { return list.Count; } }

            public int Head { get { return list._head; } }
            public int FreeHead { get { return list._freeHead; } }

            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public Node[] Nodes { get { return list._nodes; } }

        }

        #endregion

        #region fields

        private int _version;

        private int _head;
        private int _freeHead;
        private int _freeCount;

        private Node[] _nodes;

        #endregion

        #region constructors
        /// <summary>
        /// initializes a new WeakList
        /// </summary>
        public WeakList()
        {
            _nodes = new Node[4];
            for (int i = 0; i < _nodes.Length - 1; i++)
            {
                _nodes[i] = new Node(i + 1);
            }
            _nodes[3].Next = -1;
            _freeHead = 0;
            _freeCount = 4;
            _head = -1;
            _version = int.MinValue;
        }

        #endregion

        #region ICollection<T> Members
        /// <summary>
        /// Adds a new item to the list. the item cannot be null.
        /// </summary>
        public void Add(T item)
        {
            Ensure.NotNull(item, "item");
            EnsureFreespace();
            int oldFree = _freeHead;
            _freeHead = _nodes[_freeHead].Next;
            _nodes[oldFree] = new Node(item, _head);
            _head = oldFree;
            _freeCount--;
            _version++;
        }
        /// <summary>
        /// Clears the list.
        /// </summary>
        public void Clear()
        {
            _nodes = new Node[4];
            for (int i = 0; i < _nodes.Length - 1; i++)
            {
                _nodes[i] = new Node(i + 1);
            }
            _nodes[3] = new Node(-1);
            _freeHead = 0;
            _head = -1;
            _freeCount = 4;
            _version += 1;
        }
        /// <summary>
        /// returns true if the list contains the item.
        /// </summary>
        public bool Contains(T item)
        {
            Ensure.NotNull(item, "item");
            foreach (T myItem in this)
            {
                if (_comparer.Equals(item, myItem))
                {
                    return true;
                }
            }
            return false;
        }
        /// <summary>
        /// Copies all the items to the array given starting at the index given.
        /// </summary>
        public void CopyTo(T[] array, int arrayIndex)
        {
            Ensure.IndexValid(arrayIndex + Count, array, "arrayIndex");
            int index = arrayIndex;
            foreach (T item in this)
            {
                array[index] = item;
                index++;
            }
        }
        /// <summary>
        /// the number of items in the list, (may not be accurate)
        /// </summary>
        public int Count
        {
            get { return _nodes.Length - _freeCount; }
        }

        /// <summary>
        /// returns false.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }
        /// <summary>
        /// removes the item from the list.
        /// </summary>
        public bool Remove(T item)
        {
            Ensure.NotNull(item, "item");
            int curr = _head;
            int prev = -1;
            int l = _nodes.Length;
            while (l > curr && curr > -1)
            {
                if (_comparer.Equals(_nodes[curr].Target, item))
                {
                    FreeNode(prev, curr);
                    return true;
                }
                prev = curr;
                curr = _nodes[curr].Next;
            }
            return false;
        }

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// returns an enumeration of the item in the list.
        /// </summary>
        public IEnumerator<T> GetEnumerator()
        {
            int prev = -1;
            int next = _head;
            int myversion = this._version;

            while (next != -1)
            {
                if (myversion != this._version) { throw new InvalidOperationException("list has been modified"); }

                int curr = next;
                next = _nodes[curr].Next;

                object target = _nodes[curr].Target;

                if (target == null)
                {
                    FreeNode(prev, curr);
                    myversion = this._version;// cheat with version number, else we get an exception.
                }
                else
                {
                    prev = curr;
                    yield return target as T;
                }

            }
            yield break;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region private methods

        private void EnsureFreespace()
        {
            if (_freeHead == -1)
            {
                ScavengeNodes(_head);
                if (_freeHead == -1)
                {
                    ExpandNodesArray();
                }
            }
        }

        private void ExpandNodesArray()
        {
            Node[] newNodes = new Node[_nodes.Length * 2];
            Array.Copy(_nodes, 0, newNodes, 0, _nodes.Length);
            for (int i = _nodes.Length; i < newNodes.Length - 1; i++)
            {
                newNodes[i] = new Node(i + 1);
            }
            newNodes[newNodes.Length - 1] = new Node(_freeHead);
            _freeHead = _nodes.Length;
            _freeCount += _nodes.Length;
            _nodes = newNodes;
        }

        private void FreeNode(int prev, int node)
        {
            int next = _nodes[node].Next;
            if (prev == -1)
            {
                _head = next;
            }
            else
            {
                _nodes[prev].Next = next;
            }
            _nodes[node].Ref = null;
            _nodes[node].Next = _freeHead;
            _freeHead = node;
            _freeCount++;
            _version++;
        }

        private void ScavengeNodes(int head)
        {
            int curr = head;
            int prev = -1;
            int next = -1;
            int len = _nodes.Length;
            while (-1 < curr && curr < len)
            {
                next = _nodes[curr].Next;
                if (!_nodes[curr].IsAlive)
                {
                    FreeNode(prev, curr);
                }
                else
                {
                    prev = curr;
                }
                curr = next;
            }
        }

        #endregion
    }
}
